package org.czl.tree;

public class l10 {
    //二维背包模版题
    public int findMaxForm(String[] strs, int m, int n) {
        int len = strs.length;
        // 第一维表示0的数量 第二维表示 1的数量
        int[][] pre = new int[len][2];
        int index = 0;
        for(String arr : strs){
            int v = arr.length();
            for(int i = 0; i < v; i++){
                int c = arr.charAt(i);
                if(c == '0'){
                    pre[index][0]++;
                }else{
                    pre[index][1]++;
                }
            }
            index++;
        }
        //对数组进行一个预处理 初始化
        int[][][] dp = new int[len + 1][m + 1][n + 1];
        for(int i = 0; i <= m; i++){
            if(i < pre[0][0])continue;
            for(int j = 0; j <= n; j++){
                if(j >= pre[0][1]){
                    dp[1][i][j] = 1;
                }
            }
        }
        for(int k = 2; k < len; k++){
            for(int i = 0; i <= m; i++){
                if(i < pre[k][0])continue;
                for(int j = 0; j <= n; j++){
                    if(j >= pre[k][1]){
                        dp[k][i][j] = Math.max(dp[k - 1][i][j], dp[k - 1][i - pre[k][0]][j - pre[k][1]] + 1);
                    }
                }
            }
        }
        return dp[len][m][n];

    }
}
